// 希尔排序 时间复杂度：平均 O(nlogn) 最差 O(n^k) 1<k<2 不稳定 k是所选分组
/**
 * 交换法
 * @param arr{Array}
 */
function shellSort (arr) {
    let temp = 0
    let n = 1
    for (let gap = arr.length / 2; gap > 0; gap = ~~(gap / 2)) {
        for (let i = gap; i < arr.length; i++) {
            for (let j = i - gap; j >= 0; j -= gap) {
                if (arr[j] > arr[j + gap]) {
                    temp = arr[j]
                    arr[j] = arr[j + gap]
                    arr[j + gap] = temp
                }
            }
        }
        console.log(`第${n++}轮:`)
        console.log(arr.toString())
    }
}

/**
 * 移位法
 * @param arr{Array}
 */
function shellSort2 (arr) {
    let n = 1
    for (let gap = arr.length / 2; gap > 0; gap = ~~(gap / 2)) {
        for (let i = gap; i < arr.length; i++) {
            let j = i
            let temp = arr[j]
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap]
                    j -= gap
                }
                arr[j] = temp
            }
        }
        console.log(`第${n++}轮:`)
        console.log(arr.toString())
    }
}

function main () {
    let arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    // shellSort(arr)
    shellSort2(arr)
}

main()
